package otherBefore.month11;

import java.util.*;

/**
 * @author sps
 * @date 2021/12/3 13:28
 */
public class LeetCode12 {

    public int maxValueAfterReverse(int[] nums) {
        int value = 0, n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            value += Math.abs(nums[i] - nums[i + 1]);
        }
        int mx1 = 0;
        for (int i = 1; i < n - 1; i++) {
            mx1 = Math.max(mx1, Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
            mx1 = Math.max(mx1, Math.abs(nums[n - 1] - nums[i - 1]) - Math.abs(nums[i] - nums[i - 1]));
        }
        int mx2 = Integer.MIN_VALUE, mn2 = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            int x = nums[i], y = nums[i + 1];
            mx2 = Math.max(mx2, Math.min(x, y));
            mn2 = Math.min(mn2, Math.max(x, y));
        }
        return value + Math.max(mx1, 2 * (mx2 - mn2));
    }

    public int longestStrChain(String[] words) {
        int res = 0;
        Map<String, Integer> count = new HashMap<>();
        Arrays.sort(words,(a, b) -> a.length() - b.length());
        for (String word : words) {
            count.put(word,1);
            for(int i=0; i<word.length(); i++){
                String wordi = word.substring(0,i) + word.substring(i+1);
                if(count.containsKey(wordi)){
                    count.put(word,Math.max(count.get(wordi) + 1, count.get(word)));

                }
                res = Math.max(res, count.get(word));
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String str = "";
        String[] strArr = str.split(";");

    }

    public int minPushBox(char[][] grid) {
        int ans = 0;

        return ans;
    }


    public int minNumberOfFrogs(String croakOfFrogs) {
        int[] count = new int[5];
        int res = 0; int frogNum = 0;
        for(int i=0; i<croakOfFrogs.length(); i++){
            switch (croakOfFrogs.charAt(i)){
                case 'c':
                    frogNum++; res = Math.max(res,frogNum); count[0]++;
                    break;
                case 'r':
                    if(count[0] == 0){
                        return -1;
                    }
                    count[1]++; count[0]--;
                    break;
                case 'o':
                    if(count[1] == 0){
                        return -1;
                    }
                    count[2]++; count[1]--;
                    break;
                case 'a':
                    if(count[2] == 0){
                        return -1;
                    }
                    count[3]++; count[2]--;
                    break;
                case 'k':
                    if(count[3] == 0){
                        return -1;
                    }
                    count[3]--; frogNum--;
                    break;
            }
        }

        return frogNum == 0 ? -1 : res;
    }

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> keys = new HashSet<>();
        keys.add(0);
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            if(keys.contains(poll)){
                continue;
            }
            List<Integer> list = rooms.get(poll);
            keys.addAll(list);
            queue.addAll(list);
        }

        return keys.size() == rooms.size();
    }

    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        long[] preSum = new long[40001];
        for (int[] fruit : fruits) {
            preSum[fruit[0]] = fruit[1];
        }
        for(int i=1; i<startPos + k; i++){
            preSum[i] = preSum[i-1] +preSum[i];
        }
        long ans=0;
        //先向左再向右
        for(int m=0; m<k/2; m++){
            long sum = 0;
            if(k-m <= m){
                sum = preSum[startPos] - preSum[startPos - m-1];
            }else {
                sum = preSum[startPos + k - 2*m] - preSum[startPos - m-1];
            }
            ans = Math.max(ans, sum);
        }
        //先向右再向左
        for(int m=0; m<k/2; m++){
            long sum = 0;
            if(k-m <= m){
                sum = preSum[startPos + m] - preSum[startPos-1];
            }else {
                sum = preSum[startPos + m] - preSum[startPos + 2*m - k-1];
            }
            ans = Math.max(ans, sum);
        }

        return (int) ans;
    }

    public int hardestWorker(int n, int[][] logs) {
        int res = logs[0][0]; int value = logs[0][1];
        for (int i=1; i<logs.length; i++){

            int cost = logs[i][1] - logs[i-1][1];
            if(cost > value || (cost == value && logs[i][0] < res)){
                res = logs[i][0];
                value = cost;
            }
        }
        return res;
    }

    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i=1; i<n; i++){

        }
        return n;
    }


    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> resList = new ArrayList<>();

        for(int i=0; i<matrix.length; i++){
            int cur = 0;
            for(int j=0; j<matrix[0].length; j++){
                if(matrix[i][cur] > matrix[i][j]){
                    cur = j;
                }
                boolean ok = true;
                for(int k=0; k<matrix.length; k++){
                    if(matrix[i][cur] < matrix[k][cur]){
                        ok = false;
                        break;
                    }
                }
                if(ok) {
                    resList.add(matrix[i][cur]);
                }
            }
        }
        return resList;
    }
        public int minimumDifference(int[] nums, int k) {
            Arrays.sort(nums);
            int ans = Integer.MAX_VALUE;
            for(int i = k-1; i<nums.length; i++){
                ans = Integer.min(ans,nums[i] - nums[i-k+1]);
            }
            return ans;
        }

    public List<String> summaryRanges(int[] nums) {
        List<String> resList = new ArrayList<>();
        int cur = nums[0],start = 0;
        for(int i=1; i<nums.length; i++){
            if(nums[i] == cur + i - start){
                continue;
            }else {
                if(start == i - 1){
                    resList.add(String.valueOf(cur));
                }else {
                    resList.add(cur + "->" + String.valueOf(cur+i-1));
                }
                cur = nums[i];
                start = i;
            }
        }
        return resList;
    }


    public int maxSubarraySumCircular(int[] nums) {
        int max = nums[0], sum = 0, min = 0, n = nums.length, cur = 0;
        for(int i=0; i<n; i++){
            sum += nums[i];
            cur = nums[i] + Math.max(cur,0);
            max = Math.max(max,cur);
        }
        for(int i=1; i<n-1; i++){
            cur = nums[i] + Math.min(cur,0);
            min = Math.min(max,cur);
        }
        return Math.max(sum - min, max);
    }

    public int jump(int[] nums) {
        int n = nums.length;
        int[] curt = new int[n];
        for(int i=0; i<n; i++){
            for(int j=i; j<i+nums[i]; j++){
                if(curt[j] == 0){
                    curt[j] = curt[i] + 1;
                }
            }
        }
        return curt[n-1];
    }

    public boolean canJump(int[] nums) {
        int cur = 1;
        for(int i=0; i<cur; i++){
            cur--;
            cur = Integer.max(cur,nums[i]);
            if(cur == 0)return false;
        }

        return true;
    }

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int res = 0;
        int n = grid.length, m = grid[0].length;
        int[] col = new int[n];
        int[] row = new int[m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                col[i] = Integer.max(col[i],grid[i][j]);
                row[j] = Integer.max(row[j],grid[i][j]);
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                res += Integer.min(col[i],row[j]) - grid[i][j];
            }
        }
        return res;
    }


    public int maxSubArray(int[] nums) {
        int res = nums[0],cur = 0;
        for(int i=0; i<nums.length; i++){
            cur += nums[0];
            if(cur < 0){
                cur = 0;
            }else if(res < cur){
                res = cur;
            }
        }
        return res;
    }


    public int deleteAndEarn(int[] nums) {
        int numMax = 0;
        for(int i=0; i<nums.length; i++){
            numMax = Integer.max(numMax,nums[i]);
        }
        int[] sum = new int[numMax+1];
        for(int cur:nums){
            sum[cur] += cur;
        }
        return rob(sum);
    }
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Integer.max(nums[0],nums[1]);
        for(int i=2; i<n; i++){
            dp[i] = Integer.max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[n-1];
    }

    public int rob2(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Integer.max(nums[0], nums[1]);
        int[] dp = new int[n];
        int[] dpp = new int[n];
        dp[0] = dpp[0] = nums[0];
        dp[1] = dpp[1] = Integer.max(nums[0],nums[1]);
        if(n > 2)dpp[2] = Integer.max(nums[2],nums[1]);
        for(int i=2; i<n-1; i++){
            dp[i] = Integer.max(dp[i-2] + nums[i], dp[i-1]);
            dpp[i+1] = Integer.max(dpp[i-2] + nums[i], dpp[i-1]);
        }
        return Integer.max(dp[n-2], dpp[n-1]);
    }




    public String shortestCompletingWord(String licensePlate, String[] words) {
        String res = "";
        int minLength = Integer.MAX_VALUE;
        String lowerCase = licensePlate.toLowerCase();
        int[] countCase = new int[26];
        for(int i=0; i<lowerCase.length(); i++){
            if(lowerCase.charAt(i) >= 'a' && lowerCase.charAt(i) <= 'z'){
                countCase[lowerCase.charAt(i) - 'a']++;
            }
        }
        for(int i=0; i<words.length; i++){
            int[] curCount = new int[26];
            for(int j=0; j<words[i].length(); j++){
                curCount[words[i].charAt(j) - 'a']++;
            }
            boolean ok = true;
            for(int k=0; k<26; k++){
                if(curCount[k] < countCase[k]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                if(minLength > words[i].length()) {
                    minLength = words[i].length();
                    res = words[i];
                }
            }
        }

        return res;
    }



    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] res = new int[3];
        int sum1=0, sum1Idx=0, sum1Max=0;
        int sum2=0, sum2Idx2=0, sum2Idx1=0, sum2Max=0;
        int sum3=0, sum3Max=0;

        for(int i=k * 2; i<nums.length; i++){
            sum1 += nums[i-k*2];
            sum2 += nums[i-k];
            sum3 += nums[i];
            if(i > k * 3-1){
                if(sum1 > sum1Max){
                    sum1Max = sum1;
                    sum1Idx = i - k * 3 + 1;
                }
                if(sum1Max + sum2 > sum2Max){
                    sum2Max = sum2 + sum1Max;
                    sum2Idx1 = sum1Idx;
                    sum2Idx2 = i - k * 2 + 1;
                }
                if(sum2Max + sum3 > sum3Max){
                    sum3Max = sum3 + sum2Max;
                    res[0] = sum2Idx1;
                    res[1] = sum2Idx2;
                    res[2] = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }

        }
        return res;
    }


    int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int n = grid.length, m = grid[0].length;
        int[][] res = new int[n][m];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{row,col});

        while (!queue.isEmpty()){
            int[] cur = queue.poll();
            int cnt = 0;
            for(int i=0; i<4; i++){
                int dx = cur[0] + dir[i][0];
                int dy = cur[1] + dir[i][1];
                if(dx >= grid.length && dx < 0 && dy < 0 && dy >= grid[0].length)continue;
                if(grid[row][col] != grid[dx][dy]){
                    continue;
                }else {
                    cnt++;
                }
                if(res[dx][dy] == 0){
                    queue.add(new int[]{dx,dy});
                }
            }
            res[cur[0]][cur[1]] = cnt == 4 ? grid[cur[0]][cur[1]] : color;
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(res[i][j] == -1){
                    res[i][j] = color;
                }else {
                    res[i][j] = grid[i][j];
                }
            }
        }

        return res;
    }

    private void dfs(int[][] grid, int row, int col, int[][] view) {
        int cnt = 0;
        for(int i=0; i<4; i++){
            int dx = row + dir[i][0];
            int dy = col + dir[i][1];
            if(dx < grid.length && dx >= 0 && dy >= 0 && dy < grid[0].length
                    && grid[row][col] == grid[dx][dy]
                    && view[dx][dy] != 0){
                dfs(grid,dx,dy,view);
            }else {
                cnt++;
            }
        }
        view[row][col] = cnt == 4 ? grid[row][col] : -1;
    }

    public int maxRotateFunction(int[] nums) {
        int res = 0;
        int len = nums.length, sum = 0;
        int[][] presum = new int[len][2];
        for(int i=0; i<nums.length; i++){
            res += i * nums[i];
            sum += nums[i];
        }

        int cur = res;
        for(int i=0; i<len; i++){
            cur = cur - sum + len * nums[i];
            res = Integer.max(res,cur);
        }
        return res;
    }

    public int maxProduct(String[] words) {
        int len = words.length;
        int[] count = new int[len];
        for(int i=0; i<len; i++){
            for(int j=0; j<words[i].length(); j++){
                count[i] |= 1 << (words[i].charAt(j) - 'a');
            }
        }
        int res = 0;
        for(int i=1; i<len; i++){
            for(int j=0; j<i; j++){
                if((count[i] & count[j]) == 0){
                    res = Integer.max(res,words[j].length() * words[i].length());
                }

            }
        }
        return res;
    }


    public String truncateSentence(String s, int k) {
        String[] strArr = s.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<k; i++){
            sb.append(strArr[i]);
        }
        return sb.toString();
    }

    public String modifyStringa(String s) {
        char[] cha = {'a','b','c'};
        StringBuffer sb = new StringBuffer();
        sb.append("a");
        s = "a" + s + "a";
        for(int i=1; i<s.length()-1; i++){
            if('?' - s.charAt(i) == 0){
                for(int j=0; j<3; j++){
                    if(cha[j] != sb.charAt(i-2) && cha[j] != s.charAt(i+1)){
                        sb.append(cha[j]);
                        break;
                    }
                }
            }else {
                sb.append(s.charAt(i));
            }
        }
        return sb.substring(1);
    }

    public String modifyString(String s) {
        int len = s.length();
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<len; i++){
            if('?' - s.charAt(i) == 0){
                char a = 'a';
                while ((i>0 && s.charAt(i-1) == a) || (i<len-1 && s.charAt(i+1) == a)){
                    a++;
                }
                sb.append(a);
            }else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

    public int maxWidthOfVerticalArea(int[][] points) {
        int n = points.length;
        int[] idx = new int[n];
        for(int i=0; i<n; i++){
            idx[i] = points[i][0];
        }
        Arrays.sort(idx);
        int res = 0;
        for(int i=1; i<n; i++){
            res = Integer.max(res,idx[i] - idx[i-1]);
        }
        return res;
    }


    public int largestSumAfterKNegations(int[] nums, int k) {
        int res = 0,min = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0 && k > 0){
                k--;
                res = res - nums[i];
            }else if(nums[i] > 0 && k > 0){
                if(i-1 >= 0){
                    if(Math.abs(nums[i-1]) < Math.abs(nums[i])){
                        if(k%2 == 0){
                            res = res + Math.abs(nums[i-1]);
                        }else {
                            res = res - Math.abs(nums[i-1]) + nums[i];
                        }
                    }
                }else {
                    if(k%2 == 0){
                        res = res + nums[i];
                    }else {
                        res = res - nums[i];
                    }
                }
                k = 0;
            }else {
                res += nums[i];
            }
        }

        return res;
    }
}
